One or more embodiments of the present invention relate to techniques for enumerating maximal cliques of graph data by constructing and traversing a search tree through a single sequential pass on an adjacency list. The adjacency list may be generated so as to enable the at least one maximal clique to be generated in one single sequential pass.
A graph data structure is a technique for operating a computer system so as to represent data values as a set of nodes (also known as vertices or points), together with a set of connections or definitions of pairs of these nodes. These pairs are known as edges (also arcs or lines). Graph traversal (also known as graph search) is a technique for operating a computer system so as to visit, access, check and/or update each node in a graph. Such traversals may be classified by the order in which the vertices are visited.
Graph traversal or search can be a very resource intensive computing process. Conventional traversal techniques typically require random access to graph data structures or multiple passes on the graph data. Accordingly, a need arises for a technique that provides improved performance and reduced resource requirements.